This invention relates to an information processing system and its method of operation. More particularly, it relates to an associative memory device of the type having a dynamic content addressable memory (CAM).
Various processing systems perform address translations wherein a first address is translated into a second address. Related references disclose methods and hardware to accomplish these translations. Many of these references utilize content addressable memory (CAM) cells incorporated into integrated semiconductor chips. A CAM is usually described as a device in which a binary data input pattern is compared with stored data patterns to find a matching binary pattern. When the CAM detects such a match, it provides an address or location (called a match address). One scheme is to scan a random address memory (RAM) cell to find the matching data pattern.
U.S. Pat. No. 5,642,114 describes certain match inhibiting features. However, these features work on an individual bit basis rather than on a segmented match line basis. Furthermore, the reference does not use multiple or segmented match lines in each physical row.
U.S. Pat. Nos. 5,471,189; 5,517,441 and 5,659,697 describe multiple match lines for each physical row. They also appear to disclose the combining of the output of one segmented match with the next match line. The ability to disable segmented match lines through the use of signals EN0A, EN1A and NMOS transistors (514a, 514b, 516a and 516b) is shown. However, the ability to properly restore segmented match lines without the use of excessive power consumption or prolongation of the clock cycle time is not disclosed. Furthermore, both static and dynamic XOR circuits are utilized in these references.
U.S. Pat. No. 5,859,791 describes multiple match lines per physical row. However, each of the outputs from the match lines requires an additional wiring resource. Furthermore, independent control for each segmented match line is not available.
Stored information is compared with input information, causing a logic state of a first match line to be modified in response to the comparison. Generally, it is desirable to match the CAM cell height to the height of the corresponding random access memory (RAM) cell to conserve area on the surface of the silicon chip. It is also desirable to utilize the same horizontal wiring track in both the RAM and CAM arrays so there is no wasted area nor wasted wiring resources. However, this requirement makes it difficult to lay out the CAM cell since the RAM cell requires only one horizontal wiring track for a word line (WL) signal, while the CAM cell requires two horizontal wiring tracks: one for the WL signal and one for match line (ML) signal. With these two approaches shown in FIGS. 1A and 1B, it is evident that three horizontal wiring tracks are required for the CAM array: one for the WL, one for the ML, and the third horizontal wire to enable/disable the comparison. Since there is an additional wiring track per row of memory cells, these two approaches are costly in terms of area/wiring resources. The performance of these two approaches is gated by the worst case scenario: only one of the A[1:M] input signals mismatches the content within the CAM cell, so only one stack of two NMOS transistors has to pull the ML low. Therefore, there is some performance penalty for implementing this particular type of CAM using these approaches, compared to a conventional CAM where the worst case scenario is one single NMOS transistor pulling the ML low.
The present invention overcomes the difficulties of the prior art to give enhanced segmented match line control for content addressable memory. Among the advantages of the present invention are one or more of the following:
a) It provides for individualized control of each segmented match line.
b) It provides for the output of segmented match lines to be combined with the main match line through a segmented match line (SML) sense and restore circuit, thus not requiring a dedicated signal wire.
c) It includes a match inhibiting feature that works on an individual segmented match line basis.
d) It provides for the proper restore of segmented match lines.
e) It operates with all XOR circuits in a dynamic state.
f) It enhances performance while allowing for a reduction in power utilization.
g) It serves to reduce space requirements.
h) It has fewer NMOS transistors connected to each match line, thus resulting in reduced drain diffusion capacitance and less wiring capacitance, resulting in shorter evaluation time.
These and other benefits and advantages, which will become apparent, are achieved in the manner to be herein described in detail.
The invention relates to a system and a method using a content addressable memory (CAM) having a first set of input data and stored data and a second set of input data and stored data. The CAM can either perform simultaneous searches between both sets of input data against both sets of stored data, or perform searches between the second set of input data and the second set of stored data.
The CAM and the corresponding RAM typically are embedded in a semiconductor chip. The CAM preferably has a cell height that matches the cell height of the RAM for space conservation on the chip. A mismatch between the input data and the corresponding stored data causes the respective NMOS (n-type metal oxide semiconductor) transistor to pull the match line low. In one embodiment, the CAM array uses two horizontal wiring tracks. In another embodiment, the CAM array uses three horizontal wiring tracks.
The invention furthermore includes content addressable memory circuit (CAM) and the method of use. The circuit is used for separating a long match line signal into a segmented match line (SML) and a shorter match line (ML). The circuit includes two sets of CAM cells comprising set A and set B. Set A is used to evaluate the comparison of input A with the stored content of CAM set A, while set B is used for evaluating the comparison of input B with the stored contents of CAM set B. Circuitry is used to sense the value of the segmented match line (SML) and send the result to match line (ML). The circuitry restores the SML to a precharge state after the SML evaluation.
The invention further comprises a segment sense and restore circuit for a segmented match line (SML) having a charge of xe2x80x981xe2x80x99 or xe2x80x980xe2x80x99, as well as the use of the circuit. The circuit comprises means to enable an SML. This means includes a first inverter, a lead from the first inverter to the gate of a first PMOS and a second inverter in series with the first inverter. A line from the second inverter goes to the gate of a first NMOS which is in parallel with the first PMOS to form a transmission gate. A xe2x80x981xe2x80x99 signal from the enable SML will cause the gate to be open and a xe2x80x980xe2x80x99 from the enable will cause the gate to be closed. The circuit includes a charge restore means. This comprises a restore signal line gated through a second PMOS to the SML on the inlet side of the transmission gate to charge the SML. This ML is discharged when the SML signals a mismatch. This is achieved by passing the xe2x80x980xe2x80x99 on the SML through the transmission gate to the third inverter which gates a second NMOS having one lead connected to the ML. The restore signal is gated to a third NMOS which is connected to the other lead of the second NMOS for discharging the ML to ground.